1. Field of Invention
The present invention relates to encryption and decryption technologies for handling information in a confidential manner.
2. Description of the Related Art
Along with the dissemination of services that provide contents such as digitized music and videos via high-speed communication channels as represented by ADSL (Asymmetric Digital Subscriber Line) and fiber optics, there is an increasing need for preventing illegal copying and other unauthorized use of such contents.
In general, encryption technologies are applied to copyright protection systems for preventing unauthorized use of contents. For example, digital contents are encrypted with an encryption key, and then the encrypted contents are distributed via communication channels. Only user having provided with a decryption key corresponding to the encryption key are able to decrypt the encrypted contents to thereby play the original digital contents.
On the other hand, digital contents are now increasingly played on computers through the spread of personal computers. It has become progressively more common that an encryption process required for a copyright protection system is provided as an encryption program on a personal computer, and a decryption key used for decrypting encrypted contents is embedded within the encryption program beforehand.
In recent years, side channel attacks are proposed. One of the side channel attacks uses extra information leaked, during the execution of an encryption program on a computer, from the execution environment—i.e. the computer—to obtain secret information stored inside the encryption program in a confidential manner, for example, a decryption key. Processing times and power consumption are examples of such extra information used for side channel attacks.
According to Non-Patent References 1 and 2, there is a type of side channel attack known as a timing attack that focuses attention on a cache memory, which is built in a computer and used for enhancing a processing speed. Here, a cache memory (see Non-Patent Reference 3) is a memory that realizes high-speed processing. Specifically speaking, the high-speed processing is realized by storing data that the computation unit (e.g. the CPU) has obtained from the main memory once in the cache memory offering a high-speed access, and obtaining data from the cache memory thereafter when an access is made to the same data again.
A timing attack successfully determines secret information by focusing on a difference in processing times required for data acquisition from the cache memory and from the main memory.
Timing attacks are effective for encryption programs executed on CPUs having a cache memory, and target especially the AES (Advanced Encryption Standard) (described in Non-Patent Reference 4), which is an iterative block cipher using table reference operations (generally called “SBOX reference”), and the DES (Data Encryption Standard). Commonly used personal computers (e.g. PC/AT compatible machines) and smart cards having a cache memory are examples of such execution environments to which timing attacks are applicable.
The following is an outline of timing attacks.
In the AES, an EXCLUSIVE-OR operation is performed on input data and a private key (extended key), and then using the results of the operation, table reference operations are performed. Here, it is based on the assumption that, prior to the start of the encryption process, a table data array (SBOX) used in the table reference operations of the encryption process is not stored in the cache memory. Under this assumption, whether a table element of the table data array will be obtained from the cache memory or from the main memory in each table reference operation is uniquely determined depending on the input data and private key.
This means that, when values of the input data are varied, a specific table element is obtained from the cache memory in some table reference operations, and also obtained from the main memory in other table reference operations. That is to say, changing the input data results in change in the total encryption processing time.
Given this factor, a timing attack measures the total encryption processing time, and infers, based on the measured processing time, whether a table element was obtained from the cache memory or the main memory in a table reference operation of the process. Then, the timing attack analyzes the private key (extended key) based on the inference and the input data.
Such timing attacks mainly have two approaches: one is to measure the encryption processing time of each block (128 bits in the case of the AES) as described in Non-Patent Reference 1; and the other is to measure the encryption processing time of every two blocks (128 bits×2 in the case of the AES) as described in Non-Patent Reference 2. Timing attacks discussed in Non-Patent References 1 and 2 are outlined next.
The timing attack of Non-Patent Reference 1 exploits the fact that, when the same table element is accessed twice, the second access takes a shorter processing time than the first access since the table element for the second access is obtained from the cache memory. The general flow of the timing attack of Non-Patent Reference 1 is as follows.
First, contents of the cache memory are cleared each time one block is encrypted. Then, two table reference operations are focused, and a given value is assumed as to be key information having an influence on values of the input data for the two table reference operations. Under this assumption, input data whose value becomes the same in these two table reference operations is selected, and then their processing times are measured. These steps are performed on all possible values for the key information. Ultimately, a key with the shortest processing time is output as a correct key. Another two table reference operations are then focused again and the inference of the key is carried out in a similar manner.
On the other hand, the timing attack of Non-Patent Reference 2 exploits the characteristic that, with a single access to a table element in the encryption program on the main memory, actually multiple table elements are copied to the cache memory from the main memory. The general flow of the timing attack of Non-Patent Reference 2 is as follows.
First, contents of the cache memory are cleared each time two blocks are encrypted. Then, one table reference operation is focused, and a given value is assumed as to be key information having an influence on the values of the input data for the table reference operation. In the focused table reference operation for the first block, multiple table elements are copied from the main memory to the cache memory. Then, in the focused table reference operation for the second block, a value of the input data which refers to the same multiple table elements as those referred to by a value of the input data in the first block is selected (n.b. the selected value in the second block should be other than values of the input data in the first block), and the processing times are measured. These steps are performed on all possible values for the key information. Ultimately, a key with the shortest processing time is output as a correct key. Another table reference operation is then focused again and the inference of the key is carried out in a similar manner.
The encryption processing times of one/two blocks depend on input data, and timing attacks which measure processing times take advantage of this, as described above. Given this factor, a known defense against timing attacks is to cause these encryption processing times to become constant with no variation even if the input data is changed. The conventional technology described in Section 4.2 of Non-Patent Reference 5 is one example of such a defense. The outline of the conventional technology is explained next. Here, the AES is adopted as a specific applicable example of the encryption process.
The conventional technology disclosed in Non-Patent Reference 5 is characterized by adding a process independent of the input data before the execution of the AES encryption process. In the process (which is called “Cache Warming” in Non-Patent Reference 5), an access is made to each element in a table data array for table reference operations, which is used in the AES SubBytes operation. Herewith, all table elements used in the table reference operations of the AES SubBytes operation can be stored in the cache memory prior to the start of the AES encryption process, and consequently all the table elements can be obtained from the cache memory in the table reference operations of the AES SubBytes operation. As a result, the total processing time becomes consistently constant, not varying with the input data. That is, it is possible to increase resistance against timing attacks measuring processing times.
Patent Reference 1, which aims at offering an encryption apparatus having a defense function against cache-based attack cryptanalyses, and discloses means for, as to cache misses incurred during accesses to a conversion table in encryption/decryption processing, substantially equalizing the number of cache misses made in encryption/decryption of one plain text/ciphertext with that of any plain text/ciphertext.    <Non-Patent Reference 1> Y. Tsunoo, E. Tsujihara, K. Minematsu, and H. Miyauchi, “Cryptanalysis of Block Ciphers Implemented on Computers with Cache”, International Symposium on Information Theory and Its Applications (ISITA), October 2002.    <Non-Patent Reference 2> Toyohiro Tsurumaru et al., “Timing Attacks on 64-bit Block Ciphers”, The 2003 Symposium on Cryptography and Information Security (SCIS2003), 2003.    <Non-Patent Reference 3> D. A. Patterson and J. L. Hennesy, “Computer Organization and Design”, ISBN4-8222-8056-X, Published by Nikkei BP.    <Non-Patent Reference 4> Federal Information Processing Standard (FIPS) Publication 197, Nov. 26, 2001.    <Non-Patent Reference 5> D. Page, “Defending Against Cache-Based Side-Channel Attacks”, Information Security Technical Report, Vol. 8, No. 1, pp. 30-44, 2003.    <Patent Reference 1> Japanese Laid-Open Patent Application Publication No. 2004-120307.